package data_structur.Sort;

import java.util.Arrays;

/**
 * 排序：内部排序：插入排序：直接插入排序
 *                          希尔排序
 *                选择排序：简单选择排序
 *                          堆排序
 *                交换排序：冒泡排序
 *                          快速排序
 *                归并排序：
 *                基数排序：
 *     外部排序（内存和外存结合）
 */
public class SortDemo {


    // 冒泡排序（Bubble Sorting）
    // 基本思想：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较
    // 相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒
    // 冒泡排序实现&优化（根据flag，一次遍历没有发生交换则证明已经排序完成及时跳出）
    private int[] bubbleSort(int[] arr){
        int temp;
        boolean flag;
        for (int i = arr.length; i > 0; i--){
            flag = true;
            for (int j = 0; j < arr.length - 1; j++){
                if (arr[j] > arr[j+1]){
                    flag = false;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if (flag){
                break;
            }
        }
        return arr;
    }

    // 快速排序
    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int i = left, j = right, x = arr[left];
            while (i < j) {
                while (i < j && arr[j] >= x) {
                    j--;
                }
                if (i < j) {
                    arr[i++] = arr[j];
                }
                while (i < j && arr[i] < x) {
                    i++;
                }
                if (i < j) {
                    arr[j--] = arr[i];
                }
            }
            arr[i] = x;
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        }
        return arr;
    }

    // 选择排序
    private int[] selectSort(int[] arr){
        long start = System.currentTimeMillis();
        for (int j = 0; j < arr.length - 1; j++) {
            int index = j;
            int min = arr[j];
            for (int i = j; i < arr.length - 1; i++) {
                if (min > arr[i+1]){
                    min = arr[i+1];
                    index = i+1;
                }
            }
            arr[index] = arr[j];
            arr[j] = min;
        }
        long end = System.currentTimeMillis();
        System.out.println("selectSort:" + (end - start) + "ms");
        return arr;
    }

    // 插入排序
    private int[] insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            int insertInd = i - 1;
            while((insertInd >= 0) && (insertVal < arr[insertInd])){
                arr[insertInd + 1] = arr[insertInd];
                insertInd -= 1;
            }
            arr[insertInd + 1] = insertVal;
        }
        return arr;
    }


    public static void main(String[] args) {
        int[] arr = new int[10];
        for (int i = 0; i < 10; i++){
            arr[i] = (int) (Math.random() * 10);
        }
        System.out.println(Arrays.toString(arr));
        SortDemo sort = new SortDemo();

//        System.out.println(Arrays.toString(sort.bubbleSort(arr)));
//        System.out.println(Arrays.toString(sort.selectSort(arr)));

        System.out.println(Arrays.toString(sort.quickSort(arr, 0, arr.length - 1)));
    }
}
